package com.example.hot100;

import java.util.*;

/**
 * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 *
 *  说明：
 *  拆分时可以重复使用字典中的单词。
 *  你可以假设字典中没有重复的单词。
 *
 *  示例 1：
 *  输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 *
 *  示例 2：
 *  输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 *     注意你可以重复使用字典中的单词。
 *
 *  示例 3：
 *  输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 */
public class Leetcode139_WordBreak {
    public static void main(String[] args) {
        String str;
        List<String> wordDict = new ArrayList<>();

        str = "leetcode";
        wordDict.addAll(Arrays.asList("leet", "code"));

        str = "catsandog";
        wordDict.addAll(Arrays.asList("cats", "dog", "sand", "and", "cat"));

        str = "applepenapple";
        wordDict.addAll(Arrays.asList("apple", "pen"));

        System.out.println(new Solution().wordBreak(str, wordDict));
    }

    static class Solution {
        /**
         * 动态规划
         * 定义 dp[i] 表示字符串 s前 i 个字符组成的字符串 s[0..i−1] 是否能被空格拆分成若干个字典中出现的单词
         *
         * 具体做法:
         * 枚举 s[0..i−1] 中的分割点 j ，看 s[0..j−1] 组成的字符串 s1（默认 j=0 时  为空串）和 s[j..i−1] 组成的字符串 s2 是否都合法，
         * 如果两个字符串均合法，那么按照定义 s1 和 s2 拼接成的字符串也同样合法
         * 而由于计算到 dp[i] 时我们已经计算出了 dp[0..i−1] 的值(控制了只有一个字符串是可变的)，
         * 因此字符串 s1 是否合法可以直接由 dp[j] 得知，剩下的只需要看 s2 是否合法
         *
         * @param s
         * @param wordDict
         * @return
         */
        public boolean wordBreak1(String s, List<String> wordDict) {
            int len = s.length();
            boolean[] dp = new boolean[len + 1]; // dp[i]表示子串[0~i]是否能被拆成wordDict中的单词
            dp[0] = true;

            Set<String> set = new HashSet<>(wordDict);
            for (int i = 1; i <= len; i++) {
                for (int j = 0; j < i; j++) {
                    if (dp[j] && set.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }

            return dp[len];
        }

        public boolean wordBreak(String s, List<String> wordDict) {
            return wordBreak1(s, wordDict);
        }
    }
}
